package 图.最短路径;

import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-15
 */
public class 最长路径算法 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 0, 1, 1, 4, 2, 1};
        int[] arr2 = {1, 2, 2, 4, 3, 3, 3, 3};
        double[] weight = {1, 2, 3, 2, 3, 3, 2, 3};
        EdgeWeightedGraph G = new EdgeWeightedGraph(arr1.length);
        G.addGraph(arr1, arr2, weight);
        AcyclicSP dijkstraSP = new AcyclicSP(G, 0);
        System.out.println(dijkstraSP.distTo(3));
        for (DirectedEdge edge : dijkstraSP.pathTo(3)) {
            System.out.println(edge);
        }
    }
    //将权重相反，并将初始值为负无穷
    public static class AcyclicSP {
        private DirectedEdge[] edgeTo;
        private double[] distTo;


        public AcyclicSP(EdgeWeightedGraph G, int s) {
            edgeTo = new DirectedEdge[G.V()];
            distTo = new double[G.V()];
            for (int v = 0; v < G.V(); v++) {
                distTo[v] = Double.NEGATIVE_INFINITY;
            }
            distTo[s] = 0.0;
            有向加权拓扑排序.TopologicalBFS top = new 有向加权拓扑排序.TopologicalBFS(G);
            for (Integer v : top.order()) {
                relax(G, v);
            }

        }

        private void relax(EdgeWeightedGraph graph, int v) {
            for (DirectedEdge e : graph.adj(v)) {
                int w = e.to();
                if (distTo[w] < distTo[v] + e.weight()) {
                    distTo[w] = distTo[v] + e.weight();
                    edgeTo[w] = e;
                }
            }
        }
        public double distTo(int v) {
            return distTo[v];
        }

        public boolean hasPathTo(int v) {
            return distTo[v] > Double.NEGATIVE_INFINITY;
        }

        public Iterable<DirectedEdge> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<DirectedEdge> path = new Stack();
            for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
                path.push(e);
            }
            return path;
        }
    }
}
